1. Field of the Invention
This invention relates generally to biometric matching and more particularly to clustering biometric templates for efficient biometric matching.
2. Description of the Related Art
Conventional biometric matching algorithms typically require an exhaustive search of all templates to discover matches. This exhaustive search is inherently inefficient. To reduce the search time, parallel processing and hierarchical filtering approaches have been used.
Hierarchical filtering uses multiple filters that use different biometric features to incrementally reduce the number of candidate templates that need to be searched by each subsequent matching algorithm. The first filter uses the fastest but least precise matching algorithm generally based upon some gross feature in the biometric. Subsequent filters use increasingly precise, but ever slower, matching algorithms to reduce the set of biometric candidates down to the final match set.
A problem with hierarchical filtering is that different features are used for filtering than are used for the final match. This inconsistency introduces inefficiency because the filtering algorithms need to allow more candidates through to the next level.
The biometric search space may also be clustered to seek greater efficiency in the matching process. That is, biometric templates are clustered together based upon their possession of certain features. However, existing efforts to cluster biometric search spaces have been largely unsuccessful. This is likely attributable to the biometric space tending to be non-metric, which means that the triangle inequality rule does not hold, because of the fuzzy matching algorithms used to compare the features. Traditional clustering algorithms such as k-means and self organizing maps are based on distance or similarity measures. This is problematic because these algorithms assume a metric or near-metric space, and they are less effective as the space becomes less metric.
Another reason for the ineffectiveness of existing biometric clustering techniques is that one set of features is used for clustering and a different set of features is used for matching, which leads to inconsistencies. For example, an initial filtering during a matching process may be based upon the determination that a probe template includes a particular gross feature. The database of templates is then coarsely filtered based upon that particular feature. Then, additional matching algorithms that focus on different features are applied to the remaining templates (i.e., those remaining following coarse filtering) to attempt to produce a match. The problem with this approach is that the coarse filtering may be both over and under-inclusive. That is, it may filter out some viable matching candidates, or may include so many potential matches that the overall efficiency of the matching process is not adequately advanced by the coarse filtering phase.
What is needed is biometric clustering that is more efficient than conventional clustering or filtering algorithms, such as those implementing hierarchical filtering and ineffective clustering techniques.